Loj 6157 A^B problem

Posted on | Views:

带权并查集.

维护一个带权并查集, 用 $ans(x)$ 表示 $x$ 到 $x$ 的根节点路径权值异或和.

得到一个信息 $(s,t,w)$ 后,若 $s,t$ 不在同一并查集,则将两个并查集合并,并打上标记.

否则,检查 $ans(s)\oplus ans(t)$ 是否为 $t$ ,若不为 $t$ ,说明不合法.

最后若并查集数目 $>1$ ,说明有多解,否则将每个点的 $ans$ 求出后即可得到答案.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 5e5 + 10;
int n, m, fa[N], val[N], tot, siz[N], ans[N];
int Find(int st, int x)
{
	ans[st] ^= val[x];
	if (x == fa[x])
		return x;
	return Find(st, fa[x]);
}
vector<int> G[N];
void dfs(int x, int F, int &mx, int &mi)
{
	for (int y : G[x])
		if (y != F)
		{
			mx = max(mx, ans[x] ^ ans[y]);
			mi = min(mi, ans[x] ^ ans[y]);
			dfs(y, x, mx, mi);
		}
}
void solve(int id)
{
	n = read(), m = read();
	tot = n;
	for (int i = 1; i <= n; ++i)
	{
		fa[i] = i, val[i] = 0, siz[i] = 1;
		G[i].clear();
	}	
	for (int i = 1; i < n; ++i)
	{
		int u = read(), v = read();
		G[u].push_back(v), G[v].push_back(u);
	}
	bool valid = true;
	for (int i = 1; i <= m; ++i)
	{
		int s = read(), t = read(), w = read();
		ans[s] = ans[t] = 0;
		int u = Find(s, s), v = Find(t, t);
		if (siz[u] > siz[v])
			swap(u, v);
		if (u != v)
		{
			fa[u] = v;
			val[u] = ans[s] ^ ans[t] ^ w;
			--tot, siz[v] += siz[u];
		}
		else
			valid &= (ans[s] ^ ans[t]) == w;
	}
	if (!valid)
		puts("Impossible");
	else if (tot > 1)
		puts("No");
	else
	{
		int mx = 0, mi = 1 << 16;
		int rt;
		for (int i = 1; i <= n; ++i)
			ans[i] = 0, rt = Find(i, i);
		dfs(rt, 0, mx, mi);
		write(mi, ' ');
		write(mx, '\n');
	}
}
int main()
{
	int T = read();
	for (int i = 1; i <= T; ++i)
		solve(i);
	return 0;
}